package org.example.myleet.rosalind.edit;

import org.example.myleet.rosalind.utils.FastaReader;
import org.example.myleet.rosalind.utils.FastaSequence;

import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        List<FastaSequence> sequences = FastaReader.parseFastaInput(">Rosalind_39\n" +
//                "PLEASANTLY\n" +
//                ">Rosalind_11\n" +
//                "MEANLY\n");
//        List<FastaSequence> sequences = FastaReader.parseFastaInput(">Rosalind_5094\n" +
//                "CIFCVMDDQLIDIYFFRMIGCEKENIGPQWICWSHRKNSEYIAIEFIKGLRFMEQLMGGI\n" +
//                "YLCRFNHQWKDKKVVDEGFAWYGHCLTMLYMLYCDIMLLLVKDCECKIAGAAFQGHGRIW\n" +
//                "NHYLLNWCNSCMNEFQWSMCFCQCGACDVVFNKECADEGIEIKTDSCLGYQGIRRNVPWK\n" +
//                "QCSWKTPFELEWCLIPAEHQNWYLCCFNQIQDLCLLCIRSSWATTFRHGWNITWINVKNW\n" +
//                "DNSTWTRWAIGCEKILHYTHKPPFSMPGEKVTAVPQHMWALQWAMGMVRNSHRVVVRWGY\n" +
//                "FFDVMDNKWHTIQCTAATERIIEGNHMRKLTDKAWRSSRWIKLTIIRWVLTFKWQWFTML\n" +
//                "TGQPAKQRAMRLRWRNPDDCVEWICDPVDQVPEEPYHPENQMHRLRWHSYDTCSHETVNN\n" +
//                "MGNRRGSAGCSNPKVSTRDLADWHFKDGCLWGRFLCFGLKHMLCIRCDIRTRLRGGKEPE\n" +
//                "TLNSGHSAESYTPPLPMNKHTFSRNFRMLNSVYTGFIGHCNFRCARWCCGTNPRLLFNRI\n" +
//                "TDIERGEYHNPDFTKVCVWSDYGAAESYNNYWAYVGFTEYAPVLLYKDWWEPRDYGVELD\n" +
//                "ILEVYTPTIPETTHPQIECTHLRSNGALAVETSWNHSPPVDSIGTYWMKHMWYPDSSEMS\n" +
//                "AMKAQWSDKTCIPVRCAIGFWCQYYHDTMARYCFPMSEKMVDCHNCKMLWKNCITQFPLG\n" +
//                "QWYQSDRCPHNQMHWMPYTWTTHQFEKVCDHSTYAYSIVTVNCFHDERPTTASLGFDKPV\n" +
//                "YCNYHQTEHNLTH\n" +
//                ">Rosalind_1989\n" +
//                "CNLIDIYFFRAIGCERENYGPQWICWMHRKTSEYIFHPHRAQHGHIYLCRFNHQWKDKKV\n" +
//                "VEEGFAWRYTGHCLLMLYMLYCDIMLLLVKDCPCKIAGAAFQGHGRIWNHYLYAPSTRYM\n" +
//                "FNCDRDCNSCMNEFCQCGACDVVFNKEIEIKTDSCLGYQGIRGNVPWKQCSWKTPFNGEW\n" +
//                "CLIPAEHQAWYLCCFNQIQDLCELCIRESWATTFRHGWNILRCACNNNSTWTRVAYGCEK\n" +
//                "ILHYTHKPPFSMPGEKVPCSMYNIYIHMWWLQWAMGMSRNSHDNKQHTKQCTAKTERNKS\n" +
//                "SQLAGPIEGCHMPPLKLTDNAPRSSRKLTIIRWVLTFKHSMHHIQWFHMNAKQRAMRLRW\n" +
//                "RNPDHVHSKSDLDQVPELMWNACACHPYHPENQMHRLRWHSVDTCTVNNMGARRGDAGCF\n" +
//                "FSRENPKVWLEYITRDLAGWYGHCFYPKNGQQLYSCFGLAGYLFHMDLCIRCDIRTTKYW\n" +
//                "GDNLRFGKELNSGLSAEAPPLPMNKHTFSRNFRMLNSVYTCARWACITNPPARWIPMWML\n" +
//                "LFNRITDIERGEYRTENPDWTKVAAPAPKVWLLFGPHFMAGSKAWCGFTEYAPVLLYKDW\n" +
//                "WRDWDVERDILEVYTPTTPETTHPQIECTHSWSNGAMAVETSTPHHPPVDSIGNYWMKHM\n" +
//                "SEMKFQWYRVLCEECCDKTNIVRCWFFIGFWCQYQCFTHNKACFPKCEVWSHANMVDDPG\n" +
//                "RQIVIHNCDMLWKNQNYQSDACPHNQMWHANWMPRGVCLTHVVCDHSTYATKQQMHDIRP\n" +
//                "STASLGFDKPVTETHNICMFRFATH\n");
        List<FastaSequence> sequences = FastaReader.parseFastaInput(">Rosalind_6589\n" +
                "LSVWFLNEQEVIMWHKLKYPSRHTGKYHGIDQSLPAHAASWPAPYAWIHYFHSMMPDTPT\n" +
                "VYASTTTEMGRGCIWLGGACCLLQSGCFPYDYCNGFDFKEVVIGERCMMRYDSRPWDWDP\n" +
                "LVACKQKHKGPWFECAQMTRWCIPGSDIVVDIMHLESFYGDPTIFKNKYHEATPHIDIVI\n" +
                "MGVALLCASHEWFTACRCHMWPFTTNYTFWDNLQVHDIDNNMHKDATQIKLWSDRPKDTI\n" +
                "FAGIKHSVRNVPEHMGKGQRRSSMARHKRYQRTQQNEWDWVQTWGFVPTHQIVYVTDVQG\n" +
                "ERMREDVNVPCNGGRVPEGYMLCCVIDNEDACVYGAQLQDAEMFYQVKEGAVGMNYDQMS\n" +
                "HEYYPGCGRNMYCNAIYVQSHDLKPIMDWRELIYRFLLRCVPIMYTHAQGNSVRTYTFCT\n" +
                "HVIFKARDFPNVWQPNGKHILTSTNDIGSTYTEHKTNQPSVRHYYARQQIHGNRGIWPDL\n" +
                "KSHVKCNGRRQRGMYCTMMWWHNWVRIAIYQILPSCVECEDWVGRPCAECTKAFRNVGMN\n" +
                "LEAEEVWHLSMHDMWGFKLMTMFTQWCRDQIQWRKANQLMKDYERRRAFMKNTRRGWTVH\n" +
                "CHCVCNVLMTDQPVGEIHKLPTFYKTMCKQSHVTNFCNCGGFNVGGTSYINHGCYCRAFI\n" +
                "RLSQGCCVICYTADKRIDLLHIDYLTLAMIKTATYNYQCDYCKWDTNCTCQRSKNYIKFR\n" +
                "DKTTTHLMWMRLESRSYGYTICTRCPLNYFCYDCQKDTDCFFLDIKWKPLASIHYKFADY\n" +
                "EYMHPKVIQNQRMPHSLCMHKQEFYRDWHGLTKTVKQINFHKRKYRVCDEMYLYPKEKAW\n" +
                "LNWKSWPPELNHPVFKEQLAIATWAP\n" +
                ">Rosalind_9748\n" +
                "LEQEVIMWHKVMYYPSHTGKYFTNWSQAHGIDQRQKKDINCLPADMTWTNRYCAWMMPTW\n" +
                "DFNWTVYASTTTEMGAGRLMWNGACCLLQSRHGNMDPYDYCNGFDWWEVVIGERCMMRYD\n" +
                "SRVPNDWDPLVACKQKHKCFNRMVVPGIDHPVDIMHLESFYGDPTIFKNKYHEATPKILC\n" +
                "HVISVRAHLVWCHMWPFTTMLQVDIDNNMHKYATQDIFAMIKVRNVPEHMGKGQRVSSMR\n" +
                "RHKRYQRTQQNEDDKLFNTCHMCKTWGFVYITHQIVYVTDVRNPAEDVNVPMRRSTNVVP\n" +
                "EGYMLCCVGFEYQVKEGAVGMPDEVFSHEYYPWEDQTWFPSCGRAMYCNAIYVQSHNFLK\n" +
                "PACRWWHFPMDLIYPLVPIMTVREKQTHAQGNFCTHVIFKARDFPNVWPRTHGDPNGKHI\n" +
                "LTSANDIGSPYTEHSAYNAENAWAIATYNRYYARQQCHGNRIAHKSHVKCNFGMAVRRIT\n" +
                "RGMYMTMMWCHNQMIWTEPVRIKHSRIYQILPSEARQWSQTVFCEDWVGGPCAECTKHFR\n" +
                "NVGMNLTAESVSMHDMWRKMMNEPKQLAADQILQTNKPNQLMLDYQRCLAQLLIVLRAFR\n" +
                "IGWTVHCHCVCNVLMTDQPHKSPTFYGACRMNTMCKQSIVTFVNMDHYPGFCNCYINHGC\n" +
                "YCRGWQWQGHDVFIRLSQGHCVICYTSFRVDQRIDLLHDGHNKPNAPDYLDLTMIKTAPS\n" +
                "CTYNYKWDTNCTCQRSKHVGYRTYIKHLYSMRLESRQYGDTICTRCPYHWNGEFCSDCQK\n" +
                "DTDCFFLDIKWKPLFSIHYKFADYEYMHYPVIQIHKQEFYGLKQQNFFDWWRQSKRKYKG\n" +
                "GWCDEMYLFPKEKAWLNWKSWPPPLNHPVFKKQLAIATWAP\n");
        solution.findEditDistance(sequences.get(0).getSequence(), sequences.get(1).getSequence());
    }

    public void findEditDistance(String seq1, String seq2) {
        int m = seq1.length(), n = seq2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (seq1.charAt(i - 1) == seq2.charAt(j - 1)) {
                    //字符匹配，则无需增加编辑距离
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不匹配，则有3种选择，从dp[i - 1][j - 1]+1为编辑
                    //增是左部+1（dp[i][j-1]+1），删是上部+1（dp[i-1][j]+1）
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}
